package com.jzoffer;

import java.util.List;

public class TreeMirror {
    public static void main(String[] args) {
        TreeNode t1 = new TreeNode(1);
        TreeNode t2 = new TreeNode(2);
        TreeNode t3 = new TreeNode(3);
        TreeNode t4 = new TreeNode(4);
        TreeNode t5 = new TreeNode(5);
        TreeNode t6 = new TreeNode(6);

        t1.left = t2;
        t1.right = t3;
        t2.left = t4;
        t3.left = t5;
        t5.right = t6;

        Mirror(t1);
        List<Integer> list = RebuildBinaryTree.preOrder(t1);
        for(int i = 0;i < list.size();i++){
            System.out.println(list.get(i));
        }

    }

    /* 先前序遍历这棵树的每个结点，如果遍历到的结点有子结点，就交换它的两个子节点，
当交换完所有的非叶子结点的左右子结点之后，就得到了树的镜像 */
    public static void Mirror(TreeNode root) {
        if(root == null || (root.left == null && root.right == null)){
            return;
        }

        // 交换左右子树
        TreeNode leftTree = root.left;
        root.left = root.right;
        root.right= leftTree;

        if(root.left != null){
            Mirror(root.left);
        }
        if(root.right != null){
            Mirror(root.right);
        }
    }
}
